package com.myc.subjects.array;

import com.myc.subjects.utils.MapUtils;

import java.util.*;
import java.util.stream.Collectors;

/**
 * LeetCode题号：15
 *
 * 三数之和
 *
 * 给你一个包含 n 个整数的数组nums，判断nums中是否存在三个元素 a，b，c ，使得a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
 * 注意：答案中不可以包含重复的三元组。
 *
 * 示例 1：
 * 输入：nums = [-1,0,1,2,-1,-4]
 * 输出：[[-1,-1,2],[-1,0,1]]
 *
 * 示例 2：
 * 输入：nums = []
 * 输出：[]
 *
 * 示例 3：
 * 输入：nums = [0]
 * 输出：[]
 *
 * 提示：
 * 0 <= nums.length <= 3000
 * -105 <= nums[i] <= 105
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/3sum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

public class Sanshuzhihe {

    public static void main(String[] args) {
        int[] nums = new int[]{-1,0,1,2,-1,-4};
        Sanshuzhihe s = new Sanshuzhihe();
        System.out.println(s.threeSum3(nums).toString());
    }

    /**
     * 暴力法
     * 时间复杂度：O(n^3)
     * 这个方法提交LeetCode以后，在处理一个长数组的时候超出了时间限制，时间复杂度太高了，是个不好的答案
     */
    public List<List<Integer>> threeSum1(int[] nums) {
        int n = nums.length;
        //定义结果集
        List<List<Integer>> resultList = new ArrayList<>();
        for (int i = 0; i < n - 2; i++) {//第一个数遍历至倒数第三个数
            for (int j = i + 1; j < n - 1; j++) {//第二个数遍历至倒数第二个数
                for (int k = j + 1; k < n; k++) {//第三个数遍历至最后一个数
                    if (nums[i] + nums[j] + nums[k] == 0) {
                        //定义结果元素
                        List resultItem = new ArrayList(Arrays.asList(nums[i], nums[j], nums[k]));//这里需要使用Collection的子类ArrayList，而不是Array的内部类ArrayList，以便之后使用remove()方法

                        //判断结果集中有没有元素，没有就直接放入结果集，有则需要进行去重判断
                        if (resultList.size() == 0) {
                            resultList.add(resultItem);
                        } else {
                            boolean isDuplicate = false;
                            for (List item : resultList) {
                                if (equalsList(new ArrayList<>(item), new ArrayList<>(resultItem))) {//这里需要用原有的list去创建新的list，防止结果集元素被删除
                                    isDuplicate = true;
                                }
                            }
                            if (!isDuplicate) {
                                resultList.add(resultItem);//这里需要在循环外插入元素，否则会抛出java.util.ConcurrentModificationException异常
                            }
                        }
                    }
                }
            }
        }

        return resultList;
    }

    //递归方法判断两个List的元素是否相等的工具方法(默认两个list的长度是相等的)
    //该方法是我自己想出来的，应该会有不对的地方或者不够精进，请求指正。
    public boolean equalsList(List<Integer> list1, List<Integer> list2) {

        //定义边界条件退出递归
        if (list1.size() == 0) {
            return true;
        }

        //定义结果，结果需要层层传递出去
        boolean result = false;

        //定义一个长度为2的list用于存放list1与list2相等元素的下标
        List<Integer> list = new ArrayList<>();

        //比较两个list的元素，是否有相等的值。有的话对删除这两个值之后的list再进行递归比较
        outer:
        for (int i = 0; i < list1.size(); i++) {
            for (int j = 0; j < list2.size(); j++) {
                if (list1.get(i) == list2.get(j)) {
                    list.add(i);
                    list.add(j);
                    break outer;//跳出外层循环
                }
            }
        }

        //如果存在相同的值则去掉相等的两个值之后，再进行递归比较
        if (list.size() > 0) {
            list1.remove(list.get(0).intValue());
            list2.remove(list.get(1).intValue());
            result = equalsList(list1, list2);
        }

        //没有重复的值了，同时返回结果
        return result;
    }

    /**
     * 方法二：经典时间降维策略
     * 时间复杂度：O(n^2)
     * 这个方法借鉴了LeetCode第一题的利用Hashmap的contains系列方法使得时间复杂度降一个维度的策略思想，但感觉这么写挺绕的。。。
     * 还是超出了时间限制 超出时间限制是不是递归搞得鬼。。。
     */

    public List<List<Integer>> threeSum2(int[] nums) {

        int n = nums.length;

        //定义结果集
        List<List<Integer>> resultList = new ArrayList<>();

        //将两数之和与对应的List封装入Hashmap,之后再遍历map对每个键值对做两数之和的操作就OK了
        Map<Integer, List<Integer>> twoSum = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int sum = -nums[i];
            //注意只有包装类型数组才能用Arrays.asList(nums)将其转换为List，基本类型数组会被视为一个元素
            //List<Integer> list = new ArrayList(Arrays.asList(nums));//真是够坑的
            //使用StreamApi将int[]转换为List
            List<Integer> list = Arrays.stream(nums).boxed().collect(Collectors.toList());
            list.remove(i);
            twoSum.put(sum, list);
        }
        MapUtils.showMap(twoSum);

        for (Map.Entry<Integer, List<Integer>> entry : twoSum.entrySet()) {
            List<Integer> list = entry.getValue();
            int target = entry.getKey();
            Map<Integer, Integer> map = new HashMap<>();
            for (int i = 0; i < n - 1; i++) {
                if (map.containsKey(target - list.get(i))) {
                    List<Integer> resultItem = new ArrayList(Arrays.asList(-target, list.get(i), target - list.get(i)));

                    //这里使用暴力法一样的去重
                    if (resultList.size() == 0) {
                        resultList.add(resultItem);
                    } else {
                        boolean isDuplicate = false;
                        for (List item : resultList) {
                            if (equalsList(new ArrayList<>(item), new ArrayList<>(resultItem))) {//这里需要用原有的list去创建新的list，防止结果集元素被删除
                                isDuplicate = true;
                            }
                        }
                        if (!isDuplicate) {
                            resultList.add(resultItem);//这里需要在循环外插入元素，否则会抛出java.util.ConcurrentModificationException异常
                        }
                    }
                }

                map.put(list.get(i), i);
            }
        }

        return resultList;
    }

    /**
     * 方法三：双指针法
     * 时间复杂度：O(n^2)
     * 经典左右双指针方法，两个指针向中间移动，这样降低一个维度.首先要排序（非常重要，是使用双指针的前提）
     * 这题一共3个指针，先选择其中一个作为核心指针，这里我选择最小的数作为核心指针。在数组剩下的元素中选择最左和最右两个位置作为左右指针
     * 判断三数之和小于0则左指针右移，大于0则右指针左移，等于0则存入结果集，同时左右指针均移动
     */
    public List<List<Integer>> threeSum3(int[] nums){

        List<List<Integer>> resultList = new ArrayList<>();

        int n = nums.length;

        Arrays.sort(nums);//先排序，快速排序时间复杂度O(nlog^n)

        for(int i = 0; i < nums.length; i++){
            //先判断核心指针的边界情况
            if(nums[i] > 0) return resultList;
            //在核心指针遇到重复值时，跳过本次循环
            if(i > 0 && nums[i] == nums[i - 1]) continue;

            int lp = i + 1;//左指针
            int rp = n - 1;//右指针
            while(rp > lp){//当左右指针重合时终止循环
                if(nums[lp] + nums[rp] == -nums[i]){//三数之和为0

                    //将结果存入结果集
                    resultList.add(Arrays.asList(nums[i], nums[lp], nums[rp]));
                    lp++;
                    rp--;

                    //保证不会出现重复结果集，这种跳过循环的方式值得借鉴
                    while(lp < rp && nums[lp] == nums[lp - 1]) lp++;//左指针遇到相同值则左指针右移
                    while(lp < rp && nums[rp] == nums[rp + 1]) rp--;//右指针遇到相同值则右指针左移
                }
                else if(nums[lp] + nums[rp] > -nums[i])//三数之和大于0
                    rp--;
                else//三数之和小于0
                    lp++;
            }
        }
        return resultList;
    }

    //官方题解（双指针法）
    public List<List<Integer>> threeSumOfficial(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        // 枚举 a
        for (int first = 0; first < n; ++first) {
            // 需要和上一次枚举的数不相同
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }
            // c 对应的指针初始指向数组的最右端
            int third = n - 1;
            int target = -nums[first];
            // 枚举 b
            for (int second = first + 1; second < n; ++second) {
                // 需要和上一次枚举的数不相同
                if (second > first + 1 && nums[second] == nums[second - 1]) {
                    continue;
                }
                // 需要保证 b 的指针在 c 的指针的左侧
                while (second < third && nums[second] + nums[third] > target) {
                    --third;
                }
                // 如果指针重合，随着 b 后续的增加
                // 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
                if (second == third) {
                    break;
                }
                if (nums[second] + nums[third] == target) {
                    List<Integer> list = new ArrayList<Integer>();
                    list.add(nums[first]);
                    list.add(nums[second]);
                    list.add(nums[third]);
                    ans.add(list);
                }
            }
        }
        return ans;
    }

}
/**
 * 总结：
 * 坑：
 * Arrays.asList()方法：
 *  1.该方法返回的List仅能遍历访问，不能增删。
 *    解决办法：new ArrayList(rrays.asList())
 *  2.将基本数据类型的数组转换为List时，不能用这个方法。只有引用类型的数组才可以。但是基本类型的多个值可以，例如Arrays.asList(1,2,3)
 *    解决办法：将基本数据类型的数组转换为List，可以利用StreamApi来实现（详见方法二）
 *
 * 对于遍历ArrayList时想要插入元素，需要在循环外插入元素，否则会抛出java.util.ConcurrentModificationException异常
 *
 * 技巧：
 * 巧用双指针法解决数组内元素组合的问题
 * 首先要排序，使用双指针的前提
 * 在遍历时先处理边界情况
 * 在遍历时还要注意处理重复值去重的情况，这里方法三的跳过循环使用的很巧妙，以后可以借鉴
 */